#leetcode题目118：杨辉三角
#难度：简单
#时间复杂度：O(n^2)
#空间复杂度：O(n^2)
#方法：动态规划

from typing import List
class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        """
        生成杨辉三角
        给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。
        """
        res = []
        
        # 第一行：[1]
        one = [1]
        res.append(one)
        if numRows == 1:
            return res
        
        # 第二行：[1, 1]
        two = [1, 1]
        res.append(two)
        if numRows == 2:
            return res

        ## 1. 状态定义：res[i][j] 表示第i行第j列的值
        # 2. 状态转移：res[i][j] = res[i-1][j-1] + res[i-1][j]
        # 3. 边界条件：每行的第一个和最后一个元素都是1
        # 4. 计算顺序：从上到下，从左到右
        
        # 生成后续行（第3行到第numRows行）
        for i in range(2, numRows):  # 状态：第i行
            line = []
            line.append(1)  # 每行第一个元素都是1
            
            # 获取上一行
            last = res[i - 1]
            
            # 计算中间元素：当前元素 = 上一行对应位置 + 上一行对应位置+1
            for j in range(i - 1): # 状态：第j列
                line.append(last[j] + last[j + 1]) #状态转移方程
            
            line.append(1)  # 每行最后一个元素都是1
            res.append(line)
        
        return res


#测试数据
numRows = 5
#预期输出：[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
solution=Solution()
print(solution.generate(numRows))

numRows = 1
#预期输出：[[1]]
solution=Solution()
print(solution.generate(numRows))